;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname |1|) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t write repeating-decimal #f #t none #f ())))
;; Problem 1, set 05

(require rackunit)
(require rackunit/text-ui)
(require "extras.rkt")

(provide nested-to-flat)

;; ALGORITHM:
;; 1. given a nested list, check if the list has only one element.
;;    For the single element, append the (list 1), which is the initial value 
;;    of accumulator to the string.
;; 2. Else, if the list is a nested list of sections,then
;;    - on the first element append the initial value of the accumulator
;;      recur inside the first section and check if any nested subsections
;;      are present. 
;;    - For any neste subsection, append the accumulator list with 1 and
;;      repeat step 2.
;; 3. append all the recurred sections in a flat list with 
;;    accumulated sequential section number.
;;
;; The accumulator used is represented by accum. At any given point of time
;; accum stores the depth at which the current section/subsection is present inside a
;; nested section/subsection.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; A non empty list of numbers (NELON) is one of
;; -- (cons Number empty)
;;       Interp : a list with at least a single number (Number >= 0)
;; -- (cons Number NELON)
;;       Interp : represents a sequence whose first element is a Number
;;                and other elements are represented by the NELON.
;;
;; Template
;; nelon-fn : NELON -> ??
;;(define (nelon-fn nelon)
;;  (cond
;;    [(empty? (rest nelon)) (.... (first nelon))]
;;    [else (...
;;           (first nelon) 
;;           (nelon-fn (rest nelon)))]))


;; A Section is (list NELON String)
;; Interpretation :
;; Section represents a list that contains : 
;;  - NELON that represents a seuential section number.
;;  - String that represents the data.
;;
;; Template
;; section-fn : Section -> ??
;;(define (section-fn sec)
;;  (list
;;   (...(first sec))
;;   ...(second sec)))


;; A Flat-list is one of
;; -- (cons Section empty)
;;     Interp : represents a list that has only one Section.
;; -- (cons Section Flat-list)
;;     Interp : list of Sections
;;     represents a sequence,whose first element is a section and other elements
;;     are represented by Flat-list,
;;     where every another section has a section number , in sequential order.   
;;
;; Template:
;; flat-list-fn : Flat-list -> ??
;;(define (flat-list-fn f-lst)
;;  (cond
;;    [(empty?(rest f-lst)) (...(first f-lst))]
;;    [else (...
;;           (first f-lst) 
;;           (flat-list-fn (rest f-lst)))]))


;; Nested-section is 
;; (cons String Nested-subsection)
;;  Interp : represents a list containing title as a string 
;; followed by a Nested subsection
;;
;; Template:
;; nestd-section-fn : Nested-section -> ??
;;(define (nestd-section-fn nestd-section)
;;  (cons
;;   (... (first nestd-section)) 
;;   (nestd-subsection-fn (rest nestd-section))))

;; Nested-subsection is one of
;; -- empty
;;     Interp : No subsection
;; -- (cons Nested-section Nested-subsection)
;;     Interp : represents a List whose first element is a of Nested Section 
;;     and other elements are represented by Nested-subsection
;; 
;; Template:
;; nestd-subsection-fn : Nested-subsection -> ??
;;(define (nestd-subsection-fn n-sbsec)
;;  (cond
;;    [(emtpy? n-sbsec) ...]
;;    [else (... (first n-sbsec)
;;               (nestd-subsection-fn (rest n-sbsec)))]))


;; A Nested-list is one of
;; -- (cons Nested-section empty)
;;     Interp : represents a list containing only a single nested section
;; -- (cons Nested-section Nested-list)
;;     Interp : represents a list whose first element is a nested section
;;      and rest of the elemests are represented by Nested-list.
;;
;; Template:
;; nested-list-fn : Nested-list -> ??
;;(define (nested-list-fn n-lst)
;;  (cond
;;    [(empty? (rest n-lst) (... (first n-lst)))]
;;    [else (...(first n-lst)) 
;;          (nested-list-fn (rest n-lst)))]))



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; nested-to-flat : Nested-list -> Flat-list
;; takes a nested list and returns a flat list
;; Examples : See tests below
;; Strategy : Structural Decompostion [Nested-list] + accumulator [accum]
(define (nested-to-flat n-lst0)
  (local 
    (; to-flat-list : Nested-list NELON -> Flat-list
     ; INVARIANT : 
     ; n-lst is a subset of n-lst0,present at a certain depth accum in n-lst0,
     ; where accum is the result of recursion inside the nested list.
     ; Purpose : takes a Nested-list and a accumulator
     ; (non empty list of numbers), returns
     ; flat list, where the accumulator value, accum, 
     ; is appended to each of the sections/subsection in flat list. 
     (define (to-flat-list n-lst accum)
       (cond
         [(empty? (rest n-lst)) 
          (nestd-section-to-flat (first n-lst) accum)]
         [else (append 
                (nestd-section-to-flat (first n-lst) accum)
                (to-flat-list (rest n-lst) (new-value accum)))])))
    (to-flat-list n-lst0 (list 1))))


;; nestd-section-to-flat : Nested-section NELON -> Flat-list
;; takes a nested-section with list of numbers, returns
;; a Flat-list and appends the nested subsections (if present)
;; Examples : See tests below
;; Strategy : Structural Decompostion [Nested-section] 
(define (nestd-section-to-flat initial-n-section accum)
  (local 
    (; n-section-add : Nested-section NELON -> Flat-list
     ; INVARIANT:
     ; nestd-section is a subset of initial-n-section
     ; and is at depth represented by d in the initial-n-section
     ; where d is the last number of accum and initial value 1.
     ; takes a nested-section with list of numbers, returns a
     ; flat list with all the sections appended to the list.
     (define (n-section-add nestd-section accum)
       (cons (list accum (first nestd-section))
             (nestd-subsection-to-flat 
              (rest nestd-section)(append accum (cons 1 empty)))))
     
     ; nestd-subsection-to-flat : Nested-subsection NELON -> Flat-list
     ; takes a Nested-subsection with list of numbers, returns 
     ; appending all the subsections to flat list 
     ; Strategy: Structural decompostion [Nested-subsection]
     (define (nestd-subsection-to-flat n-sbsec0 accum)
       (local 
         (; n-sbsec-in-context : Nested-subsection NELON -> Flat-list
          ; INVARIANT:
          ; n-sbsec is a subset of n-sbsec0
          ; and is at depth represented by d in the n-sbsec0
          ; where d is the last number of accum and initial value 1.
          ; takes a Nested-subsection and list of numbers, 
          ; returns flat list with appended subsections.
          (define (n-sbsec-in-context n-sbsec accum)
            (cond
              [(empty? n-sbsec) empty]
              [else 
               (append (n-section-add (first n-sbsec) accum)
                       (n-sbsec-in-context (rest n-sbsec) 
                                           (new-value accum)))])))
         (n-sbsec-in-context n-sbsec0 accum))))
    (n-section-add initial-n-section accum)))


;; new-value : NELON -> NELON
;; takes a non-empty list of numbers and 
;; return a non empty list of numbers,and last number
;; of the list is incremented by 1
;; Examples : 
;; (new-value (list 1 2 3)) -> (list 1 2 4)
;; Strategy : Structural Decompostion [NELON]
(define (new-value nelon)
  (cond
    [(empty? (rest nelon)) (cons (+ 1 (first nelon)) empty)]
    [else (cons 
           (first nelon) 
           (new-value (rest nelon)))]))



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;tests

(define-test-suite nested-to-flat-tests
;; test for only a single section in the nested-list and no subsection
;; and no nested section
(check-equal?
 (nested-to-flat (list (list "only one section")))
 (list (list (list 1) "only one section"))
 "for a single section, the flat-list should contain 
   section number as (list 1) appended with the section string
(((1) only one section))")


;; test for one section having two subsections
(check-equal?
 (nested-to-flat (list (list "The first section"
                             (list "A subsection with no subsections")
                             (list "Another subsection"))))
 (list (list (list 1) "The first section")
       (list (list 1 1) "A subsection with no subsections")
       (list (list 1 2) "Another subsection"))
 " the flat-list should contain three sections appended with 
   sequential section numbers as (list 1), (list 1 1) and (list 1 2)")


;; a test where two sections are present in the nested-list
(check-equal?
 (nested-to-flat (list (list "The first section")
                       (list "Another section")))
 (list (list (list 1) "The first section")
       (list (list 2) "Another section"))
 " the flat-list should contain two sections with section
   numbers as (list 1) (list 2)")


;; test where multiple sections and subsections are present in nested-list
(check-equal?
 (nested-to-flat (list (list "The first section"
                             (list "A subsection with no subsections")
                             (list "Another subsection"
                                   (list "This is a subsection of 1.2")
                                   (list "This is another subsection of 1.2"))
                             (list "The last subsection of 1"))
                       (list "Another section"
                             (list "More stuff")
                             (list "Still more stuff"))))
 (list (list (list 1) "The first section")
       (list (list 1 1) "A subsection with no subsections")
       (list (list 1 2) "Another subsection")
       (list (list 1 2 1) "This is a subsection of 1.2")
       (list (list 1 2 2) "This is another subsection of 1.2")
       (list (list 1 3) "The last subsection of 1")
       (list (list 2) "Another section")
       (list (list 2 1) "More stuff")
       (list (list 2 2) "Still more stuff"))
 "here the flat-list should have multiple sections with section numbers 
  as (list 1), (list 1 1), (list 1 2), (list 1 2 1) (list 1 2 2)
(list 1 3) (list 2) (list 2 1) (list 2 2)"))

(run-tests nested-to-flat-tests)